package io.github.hadyang.leetcode.random;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
 *
 * <p>要求返回这个链表的深拷贝。
 *
 * <p>
 *
 * <p>示例：
 *
 * <p>输入：
 * {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
 *
 * <p>解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
 *
 * <p>提示：
 *
 * <p>你必须返回给定头的拷贝作为对克隆列表的引用。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author haoyang.shi
 * @date 2019-10-20
 */
public class Q138 {
  public Node copyRandomList(Node head) {
    if (head == null) return null;

    // insert to next line
    Node cur = head;
    while (cur != null) {
      Node tmp = new Node(cur.val, cur.next, null);
      cur.next = tmp;
      cur = tmp.next;
    }

    // insert to random line
    cur = head;
    while (cur != null) {
      cur.next.random = cur.random == null ? null : cur.random.next;
      cur = cur.next.next;
    }

    Node res = head.next;

    //split origin and copy
    cur = head;
    Node copy = cur.next;
    while (copy != null) {
      Node nextCur = copy.next;
      if (nextCur == null) {
        cur.next = null;
        copy.next = null;

        cur = null;
        copy = null;
      } else {
        cur.next = nextCur;
        copy.next = nextCur.next;

        cur = nextCur;
        copy = cur.next;
      }
    }

    return res;
  }

  @Test
  public void test() {
    Node node2 = new Node();
    node2.val = 2;
    node2.next = null;
    node2.random = node2;

    Node node1 = new Node();
    node1.val = 1;
    node1.next = node2;
    node1.random = node2;

    Node res = copyRandomList(node1);
    System.out.println(res);
  }
}
